package 力扣日常刷题.木22一月.第04天0111;

import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description
 */
public class Demo05回溯活字印刷 {


    int ans;
    char[] s;

    public int numTilePossibilities(String tiles) {
        s = tiles.toCharArray();
        Arrays.sort(s); //排序将所有使得所有相同字符在数组中连续出现
        boolean[] used = new boolean[s.length]; //used用来记录某个字符是否被使用过
        DFS(used);
        return ans;
    }


    public void dfs(boolean[] used) {
        char last = '*';
        for (int i = 0; i < s.length; i++) {
            if(!used[i] && s[i]!=last){
                ans++;
                dfs(used);
                used[i] = false;
                last = s[i];
            }
        }
    }


    public void DFS(boolean[] used) {
        char last = '*';    //在选择某一层的第一个字符时，将last设置为*，保证任意未使用过的字符均可被选择
        for (int i = 0; i < s.length; i++) {
            if (!used[i] && s[i] != last) {
                //只有被未被选择过并且不同于上一轮回溯使用的字符才会在同一层中被遍历
                ans++;
                used[i] = true;
                DFS(used);          //继续DFS遍历
                used[i] = false;    //回溯
                last = s[i];        //回溯后更新last
            }
        }
    }



}
